The present invention relates to a soft output Viterbi algorithm for use in wireless communication systems. More specifically, the present invention relates to an optimized method of obtaining the reliability values for hard decisions obtained by a Viterbi equalizer.
In wireless communication, the transmission channel introduces an Inter Symbol Interference (ISI) in the received signal. An equalizer is used in the wireless receiver to estimate the transmitted signal in the presence of the ISI. A method of equalization, known as maximum likelihood sequence estimation (MLSE), determines the sequence of symbols that is most likely to have been transmitted by the transmitter. MLSE is commonly used in wireless receivers such as the Gaussian Minimum Shift Keying (GMSK) receivers used in the Global System for Mobile (GSM) communication systems. MLSE equalizers use an algorithm known as the Viterbi algorithm, to estimate the maximum likelihood sequence.
The conventional Viterbi algorithm obtains results in the form of the most likely transmitted symbols. However, the algorithm does not provide any information regarding the reliability or likelihood of the obtained results. Therefore, the estimated transmitted symbols are called hard decisions. Further, the hard decisions obtained by the Viterbi equalizer are used by an outer decoder to obtain the decoded transmitted symbols. The performance of the outer decoder depends on the reliability of the hard decisions. The performance of the outer decoder can be enhanced by the knowledge of the reliability of the hard decisions. A modified Viterbi algorithm, known as the Soft Output Viterbi Algorithm (SOVA), obtains the reliability of the hard decisions. The conventional Viterbi algorithm is first described with reference to FIG. 1, FIG. 2 and FIG. 3. Thereafter, an implementation of the SOVA is described.
The Viterbi algorithm estimates the maximum likelihood transmitted signal at the wireless receiver, using the prior knowledge of the received signal, the channel impulse response, and the possible values of transmitted symbols. In order to use the knowledge of the possible values of the transmitted symbols, the MLSE equalizer is implemented as a state machine. The possible states of the equalizer are based on the possible values of the previous L transmitted symbols, where L is the memory of the channel, i.e., the length of the inter symbol interference introduced in the channel. Further, the state transition of the equalizer at a stage is decided by using the channel impulse response and the symbol received at that stage. To efficiently use the information available with the wireless receiver, the Viterbi algorithm uses a Viterbi trellis to represent the states and state transitions of the equalizer. The maximum likelihood sequence of the transmitted symbols is estimated by traversing the Viterbi trellis and determining a set of maximum likelihood state transitions at each stage.
Referring now primarily to FIG. 1, the Viterbi trellis for stages n and n+1 is hereinafter described. A set 102 of the previous L transmitted symbols define the Viterbi state at stage n. Similarly, a set 104 of the previous L transmitted symbols define the Viterbi state at stage n+1. Assuming two possible values {p1,p2} of the transmitted symbol, 2L Viterbi states are possible at a stage. These Viterbi states are shown as {S1, S2, . . . ,S2L}. Further, a Viterbi state set S={S1,S2, . . . ,S2L} comprises all possible Viterbi states at a stage. A possible state transition is hereinafter referred to as a branch. In a Viterbi trellis, two branches originate from each Viterbi state at a stage. Each of these branches corresponds to a possible value of the transmitted symbol. For example, branches 106 and 110, originating from Viterbi state S1 at stage n, correspond to the transmitted symbols p1 and p2, respectively. Further, two branches lead to each state at a stage. For example, branches 106 and 108 lead to Viterbi state S1 at stage n+1. A series of branches (state transitions) is hereinafter referred to as a path.
The Viterbi algorithm uses the Viterbi trellis to estimate the most likely sequence of transmitted symbols. The Viterbi algorithm involves performing a set of steps for each stage, hereinafter referred to as advancing the Viterbi trellis by a stage. The steps involve determining one surviving path leading to each Viterbi state at the stage, and taking a decision regarding a symbol at a finite number of stages N preceding the current stage. After the Viterbi trellis has been advanced by a stage, only one path for each Viterbi state at the stage survives. Therefore, only two possible paths leading to each Viterbi state at the subsequent stage remain. For example, paths 112 and 114 survive for Viterbi states S1 and S2 at stage n−1. Correspondingly, two paths leading to Viterbi state S1 remain at stage n. Once the surviving paths are determined at stage n, a decision is taken regarding a symbol at a finite number of stages N preceding stage n. The method of determining surviving paths and taking the decision is repeated at each stage of the Viterbi trellis, to estimate a maximum likelihood sequence of symbols. The method of determining surviving paths is described with reference to FIG. 2. Further, the method of estimating the maximum likelihood sequence of symbols is described with reference to FIG. 3.
Referring now primarily to FIG. 2, the method of determining surviving paths for stage n, is hereinafter described. At step 202, the received signal is convolved with the conjugate of the time-inverted channel, to obtain a symbol yn representing the received symbol at stage n. Thereafter, the first Viterbi state from Viterbi state set S is considered as state Sk at step 204. Two possible paths lead to Viterbi state Sk at a stage n+1. At step 206, a path metrics for the first possible path, leading to Viterbi state Sk at stage n+1, is obtained by using the relation
                                          CM            n                    ⁡                      (                                          I                n                            ,                              S                k                                      )                          =                                            CM                              n                -                1                                      ⁡                          (                                                I                                      n                    -                    1                                                  ,                                  S                                      k                    ′                                                              )                                +                      2            ⁢            ℛ            ⁢                          {                                                I                  n                                *                                  y                  n                                            }                                -                      2            ⁢            ℛ            ⁢                          {                                                I                  n                                *                                                      ∑                                          m                      =                      1                                        L                                    ⁢                                                            I                                              n                        -                        m                                                              *                                          x                      m                                                                                  }                                -                                                                                      I                  n                                                            2                        ⁢                          x              0                                                          (        1        )            where In denotes the transmitted symbol at stage n, Sk′ is the Viterbi state on the first possible path at stage n, CMn(In,Sk) is the path metric of a possible path leading to Viterbi state Sk at stage n+1, as obtained at stage n, CMn−1(In−1,Sk′) is the path metric of the surviving path leading to stage Sk′ at stage n, as obtained at stage n−1, set {In−m,m∈[1,L],m∈I} corresponds to Viterbi state Sk, and xm is the autocorrelation value of the channel impulse response for the time delay of m stages. Further, (In*yn) is the ISI term for stage n. At step 208, the path metric for the second possible path is similarly obtained. At step 210, the path with a higher path metric among the above two possible paths is selected as the surviving path for Viterbi state Sk at stage n+1. The possible path not selected as the surviving path, is considered as the non-surviving path at Viterbi state Sk at stage n. At step 212, it is checked whether Viterbi state Sk is the last state of Viterbi state set S. If the Viterbi state Sk is not found to be the last Viterbi state, then the next state from Viterbi state set S is considered as state Sk at step 214. Steps 206, 208 and 210 are then repeated for the new state Sk. Therefore, the surviving paths leading to all the states of Viterbi state set S is determined at stage n.
Referring now primarily to FIG. 3, the method of estimating the maximum likelihood sequence of symbols is hereinafter described. The stage of the Viterbi trellis corresponding to the first symbol to be equalized is considered as stage n, at step 302. At step 303, estimated ISI terms for all Viterbi states are pre-computed. A method of pre-computing the ISI terms is disclosed in co-pending application titled “Efficient Implementation of GSM/GPRS Equalizer” Ser. No. 10/909,232 filed Jul. 30, 2004. It will be apparent to one skilled in the art that various other methods of pre-computation of ISI terms may be employed without deviating from the spirit and scope of the present invention.
At step 304, the Viterbi trellis is then advanced by stage n, in accordance with the method described with reference to FIG. 2. Therefore, step 304 obtains 2L surviving paths, each corresponding to a Viterbi state. Thereafter, the path with the highest path metric is selected from these surviving paths as a maximum likelihood (ML) path at stage n at step 306. At step 308, a trace back along the ML path by a finite number of stages N is performed. A series of branches at multiple stages constitute a path. Also, a branch at a stage corresponds to a state transition, which, in turn, corresponds to a symbol at that stage. Therefore, a path corresponds to a series of symbols. Therefore, step 308 of tracing back determines the symbols at previous stages along the ML path. At step 310, the symbol determined at stage n−N is established as the symbol transmitted at stage n−N by tracing back. At step 312, it is verified whether stage n is the last stage to be equalized. If stage n is not found to be the last stage to be equalized, then the next stage is considered to be stage n at step 314. Steps 304 to 310 are then repeated for the new stage n. Therefore, a sequence of hard decisions, corresponding to the transmitted symbols, is obtained by the above method.
The Soft Output Viterbi Algorithm (SOVA) obtains the reliability values for the hard decisions obtained by the conventional Viterbi algorithm. An implementation of SOVA is disclosed in U.S. Pat. No. 5,181,209, publication date Jan. 19, 1993, titled “Method for generalizing the Viterbi algorithm and devices for executing the method”, to Deutsche Forschungsanstalt fur Luft-und Raumfahrt E.V. The patent provides a method of generalizing the conventional Viterbi algorithm, in which the difference costs from two arriving paths are calculated for each Viterbi state. The reliability value at the beginning of each path is set at a high value. Then the reliability value of the ML path is updated at the points where the hard decisions differ from the competing path. The updating is performed in accordance with a table, in which the prior reliability value and the difference costs are inserted into the table as the new input values. Then this new value is taken from the table and is stored, together with hard decisions, as the path memory. Therefore, additional storage at each stage is required compared to the conventional Viterbi algorithm. Finally the reliability value is read out after a decision delay from the stage which provides the result for the ML path. The above-mentioned and other methods of obtaining the reliability values for hard decisions add computational complexity to the conventional Viterbi algorithm. These methods also require additional storage at each stage. Therefore, there exists a need for an implementation of SOVA, which can obtain reliability values in a computationally efficient manner.
In digital communication systems such as GSM, the symbols are transmitted in the form of data bursts. A data burst is a set of symbols comprising control symbols, in addition to data symbols. A data burst, used in GSM, comprises two 58-symbol data sets, and a 26-symbol training sequence in the midamble. The header and footer of the GSM data burst comprise three tail symbols each. The tail symbols and the symbols of the training sequence are known in advance to the wireless receiver. For such data bursts, the Viterbi algorithm uses the known tail symbols to terminate the advancement of the Viterbi trellis. If the last L symbols of a data burst are already known to the receiver, the Viterbi state at the last stage of the trellis can be uniquely determined, since the Viterbi state at a stage depends on previous L symbols. Further, as only one Viterbi state is possible at the last stage, only one path survives at the last stage of the trellis. This path is selected as the maximum likelihood path. However, in certain wireless communication systems, the number of known tail symbols is less than the memory of the channel. For example, in the GSM data burst, three tail symbols are present. However, the memory of the channel, and hence the memory of the Viterbi trellis, is four. In such cases, more than one path survives at the last stage of the Viterbi trellis. The surviving path with highest path metric is selected as the ML path. Such a Viterbi trellis is known as the truncated Viterbi trellis. In an equalization that uses a truncated Viterbi trellis, the reliability value of the hard decision is critical for the performance of the outer decoder.
An approach to solve the above-mentioned insufficient number of tail bits problem pre-processes the received signal, to reduce the affect of ISI. The pre-processed received signal is then equalized, using a Viterbi equalizer with a memory less than the memory of the channel. Therefore, the required memory of a Viterbi equalizer can be reduced to the number of tail bits available. This approach suffers with the low accuracy of the hard decisions in estimating of the transmitted symbols. Further, for a truncated trellis, the SOVA implementation discussed above, provides the hard decisions by selecting the ML path from the paths surviving at the last stage, on the basis of the path metrics. However, they fail to provide a method of obtaining reliability values for the last L symbols. Therefore, there is a need of a method which can provide accurate hard decisions, along with a method of obtaining the reliability values for all the symbols of a data burst.